In mathematical logic, the Peano axioms (, "Peano". Random House Webster's Unabridged Dictionary. ), also known as the Dedekind–Peano axioms or the Peano postulates, are for the presented by the 19th-century Italian mathematician Giuseppe Peano. These axioms have been used nearly unchanged in a number of metamathematics investigations, including research into fundamental questions of whether number theory is consistent and complete.
The axiomatization of arithmetic provided by Peano axioms is commonly called Peano arithmetic.
The importance of formalizing arithmetic was not well appreciated until the work of Hermann Grassmann, who showed in the 1860s that many facts in arithmetic could be derived from more basic facts about the successor operation and induction. In 1881, Charles Sanders Peirce provided an axiomatization of natural-number arithmetic. In 1888, Richard Dedekind proposed another axiomatization of natural-number arithmetic, and in 1889, Peano published a simplified version of them as a collection of axioms in his book The principles of arithmetic presented by a new method ().
The nine Peano axioms contain three types of statements. The first axiom asserts the existence of at least one member of the set of natural numbers. The next four are general statements about equality; in modern treatments these are often not taken as part of the Peano axioms, but rather as axioms of the "underlying logic". The next three axioms are first-order statements about natural numbers expressing the fundamental properties of the successor operation. The ninth, final, axiom is a second-order statement of the principle of mathematical induction over the natural numbers, which makes this formulation close to second-order arithmetic. A weaker first-order system is obtained by explicitly adding the addition and multiplication operation symbols and replacing the second-order induction axiom with a first-order axiom schema. The term Peano arithmetic is sometimes used for specifically naming this restricted system.
The Peano axioms define the arithmetical properties of natural numbers, usually represented as a set N or The non-logical symbols for the axioms consist of a constant symbol 0 and a unary function symbol S.
The first axiom states that the constant 0 is a natural number:
Peano's original formulation of the axioms used 1 instead of 0 as the "first" natural number, while the axioms in Formulario mathematico include zero.
The next four axioms describe the equality relation. Since they are logically valid in first-order logic with equality, they are not considered to be part of "the Peano axioms" in modern treatments.
The remaining axioms define the arithmetical properties of the natural numbers. The naturals are assumed to be closed under a single-valued "successor" function S.
[File:Domino, Simon Fraser UniversityGerardo con Diaz, Mathematical Induction , Harvard University However, axioms 1–8 are satisfied by the set of all dominoes—whether light or dark—taken together.The non-contiguous set satisfies axiom 1 as it has a 0 element, 2–5 as it doesn't affect equality relations, 6 as all pieces have a successor, axiom 7 as no two dominos topple, or are toppled by, the same piece, and axiom 8 as every domino bar the first light domino is toppled by another domino. The 9th axiom (induction) limits N to the chain of light pieces ("no junk") as only light dominoes will fall when the nearest is toppled. ]] Axioms 1, 6, 7, 8 define a unary representation of the intuitive notion of natural numbers: the number 1 can be defined as S(0), 2 as S( S(0)), etc. However, considering the notion of natural numbers as being defined by these axioms, axioms 1, 6, 7, 8 do not imply that the successor function generates all the natural numbers different from 0.
The intuitive notion that each natural number can be obtained by applying successor sufficiently many times to zero requires an additional axiom, which is sometimes called the axiom of induction.
The induction axiom is sometimes stated in the following form:
In Peano's original formulation, the induction axiom is a second-order axiom. It is now common to replace this second-order principle with a weaker first-order induction scheme. There are important differences between the second-order and first-order formulations, as discussed in the section below.
&= S(a + 0) & \mbox{using (2)} \\ &= S(a), & \mbox{using (1)} \\\\ a + 2 &= a + S(1) & \mbox{by definition} \\
&= S(a + 1) & \mbox{using (2)} \\ &= S(S(a)) & \mbox{using } a + 1 = S(a) \\\\ a + 3 &= a + S(2) & \mbox{by definition} \\
&= S(a + 2) & \mbox{using (2)} \\ &= S(S(S(a))) & \mbox{using } a + 2 = S(S(a)) \\\text{etc.} & \\ \end{align}
To prove commutativity of addition, first prove and , each by induction on . Using both results, then prove by induction on . The structure is a commutative monoid with identity element 0. is also a cancellative magma, and thus embedding in a group. The smallest group embedding N is the .
To show that is also the multiplicative left identity requires the induction axiom due to the way multiplication is defined:
Therefore, by the induction axiom is the multiplicative left identity of all natural numbers. Moreover, it can be shownFor formal proofs, see e.g. Inductive proofs of properties of add, mult from recursive definitions.pdf. that multiplication is commutative and distributive law addition:
Thus, is a commutative semiring.
This relation is stable under addition and multiplication: for , if , then:
Thus, the structure is an ordered ring; because there is no natural number between 0 and 1, it is a discrete ordered semiring.
The axiom of induction is sometimes stated in the following form that uses a stronger hypothesis, making use of the order relation "≤":
This form of the induction axiom, called strong induction, is a consequence of the standard formulation, but is often better suited for reasoning about the ≤ order. For example, to show that the naturals are —every empty set subset of N has a least element—one can reason as follows. Let a nonempty be given and assume X has no least element.
Thus, by the strong induction principle, for every , . Thus, , which contradiction X being a nonempty subset of N. Thus X has a least element.
f(0_A) &= 0_B \\ f(S_A (n)) &= S_B (f (n)) \end{align} and it is a bijection. This means that the second-order Peano axioms are categorical. (This is not the case with any first-order reformulation of the Peano axioms, below.)
The set of natural numbers N is defined as the intersection of all sets closed under s that contain the empty set. Each natural number is equal (as a set) to the set of natural numbers less than it:
0 &= \emptyset \\ 1 &= s(0) = s(\emptyset) = \emptyset \cup \{ \emptyset \} = \{ \emptyset \} = \{ 0 \} \\ 2 &= s(1) = s(\{ 0 \}) = \{ 0 \} \cup \{ \{ 0 \} \} = \{ 0 , \{ 0 \} \} = \{ 0, 1 \} \\ 3 &= s(2) = s(\{ 0, 1 \}) = \{ 0, 1 \} \cup \{ \{ 0, 1 \} \} = \{ 0, 1, \{ 0, 1 \} \} = \{ 0, 1, 2 \} \end{align} and so on. The set N together with 0 and the successor function satisfies the Peano axioms.
Peano arithmetic is equiconsistent with several weak systems of set theory. One such system is ZFC with the axiom of infinity replaced by its negation. Another such system consists of general set theory (extensionality, existence of the empty set, and the axiom of adjunction), augmented by an axiom schema stating that a property that holds for the empty set and holds of an adjunction whenever it holds of the adjunct must hold for all sets.
Then C is said to satisfy the Dedekind–Peano axioms if US1( C) has an initial object; this initial object is known as a natural number object in C. If is this initial object, and is any other object, then the unique map is such that
u (0) &= 0_X, \\ u (S x) &= S_X (u x). \end{align} This is precisely the recursive definition of 0 X and S X.
Although it is widely claimed that Gödel's theorem rules out the possibility of a finitistic consistency proof for Peano arithmetic, this depends on exactly what one means by a finitistic proof. Gödel himself pointed out the possibility of giving a finitistic consistency proof of Peano arithmetic or stronger systems by using finitistic methods that are not formalizable in Peano arithmetic, and in 1958, Gödel published a method for proving the consistency of arithmetic using type theory. In 1936, Gerhard Gentzen gave a proof of the consistency of Peano's axioms, using transfinite induction up to an Ordinal number called ε0. Gentzen explained: "The aim of the present paper is to prove the consistency of elementary number theory or, rather, to reduce the question of consistency to certain fundamental principles". Gentzen's proof is arguably finitistic, since the transfinite ordinal ε0 can be encoded in terms of finite objects (for example, as a Turing machine describing a suitable order on the integers, or more abstractly as consisting of the finite trees, suitably linearly ordered). Whether or not Gentzen's proof meets the requirements Hilbert envisioned is unclear: there is no generally accepted definition of exactly what is meant by a finitistic proof, and Hilbert himself never gave a precise definition.
The vast majority of contemporary mathematicians believe that Peano's axioms are consistent, relying either on intuition or the acceptance of a consistency proof such as Gentzen's proof. A small number of philosophers and mathematicians, some of whom also advocate ultrafinitism, reject Peano's axioms because accepting the axioms amounts to accepting the infinite collection of natural numbers. In particular, addition (including the successor function) and multiplication are assumed to be total. Curiously, there are self-verifying theories that are similar to PA but have subtraction and division instead of addition and multiplication, which are axiomatized in such a way to avoid proving sentences that correspond to the totality of addition and multiplication, but which are still able to prove all true theorems of PA, and yet can be extended to a consistent theory that proves its own consistency (stated as the non-existence of a Hilbert-style proof of "0=1").
First-order axiomatizations of Peano arithmetic have another technical limitation. In second-order logic, it is possible to define the addition and multiplication operations from the successor operation, but this cannot be done in the more restrictive setting of first-order logic. Therefore, the addition and multiplication operations are directly included in the signature of Peano arithmetic, and axioms are included that relate the three operations to each other.
The following list of axioms (along with the usual axioms of equality), which contains six of the seven axioms of Robinson arithmetic, is sufficient for this purpose:
In addition to this list of numerical axioms, Peano arithmetic contains the induction schema, which consists of a recursively enumerable and even decidable set of axioms. For each formula in the language of Peano arithmetic, the first-order induction axiom for φ is the sentence
where is an abbreviation for y1,..., y k. The first-order induction schema includes every instance of the first-order induction axiom; that is, it includes the induction axiom for every formula φ.
The theory defined by these axioms is known as PA−. It is also incomplete and one of its important properties is that any structure satisfying this theory has an initial segment (ordered by ) isomorphic to . Elements in that segment are called standard elements, while other elements are called nonstandard elements.
Finally, Peano arithmetic PA is obtained by adding the first-order induction schema.
Closely related to the above incompleteness result (via Gödel's completeness theorem for FOL) it follows that there is no algorithm for deciding whether a given FOL sentence is a consequence of a first-order axiomatization of Peano arithmetic or not. Hence, PA is an example of an undecidable theory. Undecidability arises already for the existential sentences of PA, due to the negative answer to Hilbert's tenth problem, whose proof implies that all computably enumerable sets are , and thus definable by existentially quantified formulas (with free variables) of PA. Formulas of PA with higher quantifier rank (more quantifier alternations) than existential formulas are more expressive, and define sets in the higher levels of the arithmetical hierarchy.
When interpreted as a proof within a first-order set theory, such as ZFC, Dedekind's categoricity proof for PA shows that each model of set theory has a unique model of the Peano axioms, up to isomorphism, that embeds as an initial segment of all other models of PA contained within that model of set theory. In the standard model of set theory, this smallest model of PA is the standard model of PA; however, in a nonstandard model of set theory, it may be a nonstandard model of PA. This situation cannot be avoided with any first-order formalization of set theory.
It is natural to ask whether a countable nonstandard model can be explicitly constructed. The answer is affirmative as Skolem in 1933 provided an explicit construction of such a nonstandard model. On the other hand, Tennenbaum's theorem, proved in 1959, shows that there is no countable nonstandard model of PA in which either the addition or multiplication operation is computable. This result shows it is difficult to be completely explicit in describing the addition and multiplication operations of a countable nonstandard model of PA. There is only one possible order type of a countable nonstandard model. Letting ω be the order type of the natural numbers, ζ be the order type of the integers, and η be the order type of the rationals, the order type of any countable nonstandard model of PA is , which can be visualized as a copy of the natural numbers followed by a dense linear ordering of copies of the integers.
|
|